package com.base.leetcode;

import com.base.dataStructure.Tree.TreeNode;

/**
 * @Author: hdhao
 * @Create: 2023/4/9 - 14:48
 * @Version: v1.0
 */
//根据二叉搜索树前序遍历结果构造二叉搜索树
public class Leetcode1008 {

    public TreeNode bstFromPreOrder(int[] preOrder) {
        TreeNode root = new TreeNode(preOrder[0]);
        for (int i = 1; i < preOrder.length; i++) {
            int val = preOrder[i];
            insert(root,val);
        }
        return root;
    }

    private TreeNode insert(TreeNode node, int val) {
        if (node == null) {
            return new TreeNode(val);
        }
        if (val < node.val) {
            node.left = insert(node.left, val);
        } else if (node.val < val) {
            node.right = insert(node.right, val);
        }
        return node;
    }
    //--------------------第二种方法-------------------------
    /*
        依次处理preOrder中的每个值，返回创建好的节点或null
        1.如果超过上限,返回null,作为孩子返回
        2.如果没超过上限,创建节点,并设置其左右孩子,左右孩子完整后返回
     */
    int i = 0;
    private TreeNode insert(int[] preOrder, int max) {
        if (i == preOrder.length) {
            return null;
        }
        int val = preOrder[i];
        if (val > max) {
            return null;
        }
        TreeNode node = new TreeNode(val);
        i++;
        node.left = insert(preOrder, val);
        node.right = insert(preOrder, max);
        return node;
    }

    public TreeNode bstFromPreOrder1(int[] preOrder) {
        return insert(preOrder, Integer.MAX_VALUE);
    }
    //------------------------分治法-------------------------
    /*
        preOrder: 8,5,1,7,10,12
        根 8 左 5,1,7 右 10,12
        根 5 左 1 右 7
        根 10 右 12
     */
    //分治法求解
    public TreeNode bstFromPreOrder2(int[] preOrder) {
        return partition(preOrder, 0, preOrder.length - 1);
    }
    public TreeNode partition(int[] preOrder, int start, int end) {
        if (start > end) {
            return null;
        }
        TreeNode root = new TreeNode(preOrder[start]);
        int index = start + 1;
        while (index <= end) {
            if (preOrder[index] > root.val) {
                break;
            }
            index++;
        }
        //index 就是右子树的起点
        root.left = partition(preOrder,start + 1, index - 1);
        root.right = partition(preOrder, index, end);
        return root;
    }
}
